package com.leetcode.algorithm.y22.m08.w1;

import java.util.HashSet;
import java.util.Set;

/**
 * 200. 岛屿数量
 * 
 * https://leetcode.cn/problems/number-of-islands/
 * 
 * @author jie.deng
 *
 */
class Question0200Solution03 {

	public int numIslands(char[][] grid) {
		// DFS
		int cnt = 0;
		int cols = grid[0].length;
		Set<Integer> visitedSet = new HashSet<>();
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < cols; j++) {
				if (grid[i][j] == '1' && visitedSet.add(i * cols + j)) {
					cnt++;
					dfs(grid, visitedSet, i, j);
				}
			}
		}
		return cnt;
	}

	private void dfs(char[][] grid, Set<Integer> visitedSet, int row, int col) {
		int cols = grid[0].length;
		int[][] directions = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
		for (int[] dir : directions) {
			int r = row + dir[0];
			int c = col + dir[1];
			if (r >= 0 && r < grid.length && c >= 0 && c < cols) {
				if (grid[r][c] == '1' && visitedSet.add(r * cols + c)) {
					dfs(grid, visitedSet, r, c);
				}
			}
		}
	}

}